package Top101;

import java.util.*;

public class Test_9_27 {

    //滑动窗口的最大值
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if(size == 0 || size > num.length) return ret;

        Deque<Integer> deque = new LinkedList<>();
        int left = 0;
        int right = 0;
        while(left <= num.length - size ) {
            if(right - left < size) {
                if(deque.isEmpty()) {
                    deque.addFirst(num[right]);
                } else {
                    if(num[right] > deque.peekFirst()) {
                        while(!deque.isEmpty()) {
                            deque.poll();
                        }
                        deque.addFirst(num[right]);
                    } else {
                        if(num[right] <= deque.peekLast()) {
                            deque.addLast(num[right]);
                        } else {
                            while(deque.peekLast() < num[right]) {
                                deque.pollLast();
                            }
                            deque.addLast(num[right]);
                        }

                    }
                }
                right++;
            } else {
                ret.add(deque.peekFirst());
                if(num[left] == deque.peekFirst()) {
                    deque.pollFirst();
                }
                left++;
            }
        }
        return ret;
    }

}
